package com.duoduo.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm
 * @description: 螺旋矩阵54
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 * @author: chaidl  ！
 * @create: 2022-05-08 22:11
 */
public class 螺旋矩阵54 {
	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> list = new ArrayList<Integer>();
		if (matrix == null || matrix.length == 0) {
			return list;
		}
		int x = matrix.length;
		int y = matrix[0].length;
		//层数指示器
		int plies = 0;
		//总层数
		int count = (Math.min(x, y) + 1) / 2;
		//从0，0开始依次遍历
		while (plies < count) {
			/*每层矩阵的起始元素都是matrix[plies][plies]*/
			/*从左至右，到matrix[plies][colLength-1-plies]时停止，准备转向*/
			for (int j = plies; j < y - plies; j++) {
				list.add(matrix[plies][j]);
			}
			/*从上往下，本列的第一个元素已经在上面的“从左至右”中处理了，
			 * 所以行从应该从plies+1开始，列(colLength-1-plies)维持不变，
			 * 起始元素就是matrix[plies+1][colLength-1-plies]，
			 * 到matrix[rowLength-1-plies][colLength-1-plies]时停止，准备转向*/
			for (int j=plies+1;j<x-plies;j++){
				list.add(matrix[j][(y-1)-plies]);
			}
			/*从右往左，本行的第一个元素已经在上面的“从上往下”中处理了，
			 * 所以列应该从(colLength-1-plies)-1开始，行维持不变，
			 * 起始元素就是matrix[rowLength-1-plies][(colLength-1-plies)-1]，
			 * 到matrix[rowLength-1-plies][plies]时停止，准备转向*/
			/*rowLength-1-plies == plies，表示本层只有单行，不必再处理*/
			for (int j=(y-1-plies)-1;j>=plies && (x-1-plies != plies);j--){
				list.add(matrix[(x-1) - plies][j]);
			}
			/*从下往上，本列的第一个元素已经在上面的“从右往左”中处理了，
			 * 所以行从应该从(rowLength-1-plies)-1开始，列(plies)维持不变，
			 * 起始元素就是matrix[(rowLength-1-plies)-1][plies]，
			 * 到matrix[plies+1][plies]时停止*/
			/*colLength-1-plies != plies，表示本层只有单列，不必再处理*/
			for (int j = (x-1)-(plies+1); j >= plies+1 && (y-1-plies != plies); j--) {
				list.add(matrix[j][plies]);
			}
			plies++; /*层数累加*/
		}
		return list;
	}
	//个人感觉这种好理解一点
	public List<Integer> spiralOrder2(int[][] matrix) {
		List<Integer> order = new ArrayList<Integer>();
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return order;
		}
		int rows = matrix.length, columns = matrix[0].length;
		int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
		//顺时针旋转有两种情况，行不变和列不变
		while (left <= right && top <= bottom) {
			//从左到右 行不变 所以列++ 依次为 (top,left) 到 (top,right)
			for (int column = left; column <= right; column++) {
				order.add(matrix[top][column]);
			}
			//从上往下列不变，所以行++ (top+1,right) 到 (bottom,right)(
			for (int row = top + 1; row <= bottom; row++) {
				order.add(matrix[row][right]);
			}
			//在这里不能相等，
			// 如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1)到 (bottom,left+1)，
			// 以及从下到上遍历左侧元素，依次为 (bottom,left)到 (top+1,left)
			if (left < right && top < bottom) {
				//从右往左
				for (int column = right - 1; column > left; column--) {
					order.add(matrix[bottom][column]);
				}
				//从下往上
				for (int row = bottom; row > top; row--) {
					order.add(matrix[row][left]);
				}
			}
			left++;
			right--;
			top++;
			bottom--;
		}
		return order;
	}
}
